package leetcode.calc._06_07;

import org.springframework.util.Assert;

/**
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * <p>
 * 进阶：你能尝试使用一趟扫描实现吗？
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：head = {1,2,3,4,5}, n = 2
 * 输出：{1,2,3,5}
 * 示例 2：
 * <p>
 * 输入：head = {1}, n = 1
 * 输出：{}
 * 示例 3：
 * <p>
 * 输入：head = {1,2}, n = 1
 * 输出：{1}
 *  
 * <p>
 * 提示：
 * <p>
 * 链表中结点的数目为 sz
 * 1 <= sz <= 30
 * 0 <= Node.val <= 100
 * 1 <= n <= sz
 * <p>
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _07_13_019_删除链表的倒数第N个结点_01_My {
    public static void main(String[] args) {
        Solution sol = new _07_13_019_删除链表的倒数第N个结点_01_My().new Solution();
        if (true) {
            int[] param = {1, 2, 3, 4, 5};
            int param2 = 2;
            String rel = "{1,2,3,5}";
            ListNode node = ListNode.crtNode(param);
            ListNode resNode = sol.removeNthFromEnd(node, param2);
            String res = resNode == null ? "{}" : resNode.toString();
            Assert.isTrue(res.equals(rel), String.format("\n%s !=\n%s", res, rel));
        }
        if (true) {
            int[] param = {1};
            int param2 = 1;
            String rel = "{}";
            ListNode node = ListNode.crtNode(param);
            ListNode resNode = sol.removeNthFromEnd(node, param2);
            String res = resNode == null ? "{}" : resNode.toString();
            Assert.isTrue(res.equals(rel), String.format("\n%s !=\n%s", res, rel));
        }
        if (true) {
            int[] param = {1,2};
            int param2 = 1;
            String rel = "{1}";
            ListNode node = ListNode.crtNode(param);
            ListNode resNode = sol.removeNthFromEnd(node, param2);
            String res = resNode == null ? "{}" : resNode.toString();
            Assert.isTrue(res.equals(rel), String.format("\n%s !=\n%s", res, rel));
        }
    }


    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int num) {
            int arrLen = num + 1;
            ListNode[] nodes = new ListNode[arrLen];
            ListNode tmp = head;
            int curIndex = 0;
            int curNum = 0;
            while (tmp != null) {
                nodes[curIndex] = tmp;
                tmp = tmp.next;
                curNum++;
                curIndex++;
                if (curIndex >= arrLen) {
                    curIndex%=arrLen;
                }
            }
            if (curNum == num) {
                ListNode res = head.next;
                head.next = null;
                return res;
            }
            // 移除 node的 上一级 index
            ListNode father = nodes[curIndex];
            ListNode remove = father.next;
            father.next = remove.next;
            remove.next = null;
            return head;
        }
    }

}
